#### فصل ۹
#### مورد مطالعه: بازی واژه
این بخش مورد مطالعه دوم را ارائه می دهد، که دربرگیرنده حل معمای واژگان بوسیله جستجو برای واژگان می‌باشد که ویژگی‌های خاصی دارند. برای نمونه، ما درازترین عبارت واروخوانه (palindrome) در انگلیسی را پیدا خواهیم کرد و واژگانی را جستجو خواهیم کرد که حروف شان به ترتیب الفبایی باشند. و من یک برنامه‌ریزی دیگر برای توسعه برنامه ارائه خواهم کرد: کوتاه کردن یک مسأله حل شده پیشین.
#### 9.1 خواندن فهرست های واژه
برای تمرین‌های در این بخش ما یک فهرست از واژگان انگلیسی نیاز داریم. لیست های واژگان بسیاری در وب هستند، ولی آنی که بیشتر درخور این کار ما می‌باشد یکی از فهرست های واژگانی است که بدست Grady Ward به عنوان بخشی از پروژه موبی (http://en.wikipedia.org/wiki/Moby_project) گردهم آوری شده است. که آن لیستی از 113,809 کلمه متقاطع می باشد؛ یعنی این که، واژه‌هایی که در معماهای کلمات متقاطع و دیگر بازی با واژه‌ها معتبر شمرده می شوند. در مجموعه موبی، نام فایل 113809of.fic می باشد؛ شما می‌توانید یک کپ، با یک نام ساده‌تر words.txt، از نشانی http://thinkpython2.com/code/words.txt دریافت کنید.
این فایل متن خام است، بنابراین شما می‌توانید آنرا با یک ویرایشگر متنی باز کنید، ولی همچنین می‌توانید آنرا از درون Python بخوانید. تابع درونی (built-in) open نام فایل را به عنوان یک پارامتر می‌گیرد و یک شیء file بر‌می‌گرداند که می‌توانید از آن برای خواندن فایل بهره ببرید.
>>> fin = open('words.txt')
در این عبارت واژه fin یک نام رایج برای یک شیء file برای ورودی می باشد. شیء file چندین روش برای خواندن، دربردارنده readline، فراهم می‌کند که کاراکترها را از فایل تا زمانی که به یک newline برسد می‌خواند و نتیجه را به عنوان یک رشته بر‌می‌گرداند.
>>> fin.readline()
'aa\r\n'
نخستین واژه در این لیست خاص “aa” می باشد. دنباله \r\n دو کاراکتر فضای خالی را نمایش می دهند، یک carriage return و یک newline، که این واژه را از بعدی جدا می کند.
شیء file رد اینکه کجای فایل هستیم را نگه می دارد، بنابراین اگر دوباره readline را صدا بزنید، می‌توانید واژه بعدی را بخوانید:
>>> fin.readline()
'aah\r\n'
واژه بعدی “aah” است. اگر فضای خالی آزارتان می دهد، می‌توانید خود را از دست آن با متد strip رشته برهانید:
>>> line = fin.readline()
>>> word = line.strip()
>>> word
'aahed'
همچنین می‌توانید از شیء file به عنوانی بخشی از حلقه for بکار بگیرید. این برنامه فایل words.txt را می‌خواند و همه واژه‌ها را چاپ می کند، هرکدام در یک خط:
fin = open('words.txt')
for line in fin:
word = line.strip()
print(word)
#### ۹.۲ تمرین ها
حل این تمرین‌ها در بخش بعدی آورده شده اند. بهتر است پیش از اینکه راه حل‌ها را بخوانید برای هر کدام را دست کم یکبار تلاش کنید.
تمرین ۹.۱. برنامه‌ای بنویسید که فایل words.txt را می‌خواند و تنها واژگانی را چاپ می‌کند که دارای بیش از ۲۰ حرف می‌باشند (بدون شمارش فضای خالی).
تمرین ۹.۲. در سال ۱۹۳۹ ارنست وینسنت رایت یک رمان ۵۰،۰۰۰ واژه‌ای را منتشر کرد که Gadsby نام دارد که دربردارنده حرف “e” نیست. چون “e” رایج ترین حرف در انگلیسی است، کار آسانی نبوده است.
در واقع، ساخت یک اندیشه بدون بکار بردن رایج ترین نماد دشوار است. در آغاز کند پیش می رود، ولی با احتیاط و ساعت‌ها آموزش می‌توانید کم کم روان شوید.
بسیار خب، دیگر ادامه نمی دهم.
یک تابع به نام has_no_e بنویسید که چنانچه واژه داده شده دارای حرف “e” نباشد True برگرداند.
برنامه تان را از بخش پیشین به گونه‌ای اصلاح کنید که تنها واژگانی را چاپ کند که هیچ “e” در آنها نیست و درصد واژگانی را که در لیست هیچ حرف “e” ندارند را محاسبه کند.
تمرین ۹.۳. یک تابع به نام avoids بنویسید که یک واژه و یک رشته از حروف ممنوعه را به عنوان پارامتر بگیرد و چنانچه آن واژه هیچ یک از حروف ممنوعه را دربرنداشته باشد True برگرداند.
برنامه خود را به گونه‌ای اصلاح کنید که از کاربر بخواهد یک رشته از حروف ممنوعه را وارد کند و سپس شمار واژگانی که هیچ یک از آنها ندارند چاپ کند. آیا می‌توانید یک ترکیب از ۵ حروف ممنوعه را پیدا کنید که واژگان کمتری را از رده خارج می کند.
تمرین ۹.۴. یک تابع به نام uses_only بنویسید که یک واژه و یک رشته از حروف را به عنوان پارامتر می‌گیرد و چنانچه اگر آن واژه تنها دارای حروف در آن رشته باشند True برگرداند. آیا می‌توانید یک جمله تنها با بکارگیری از حروف acefhlo بسازید؟ بغیر “؟Hoe alfalfa“
تمرین ۹.۵. یک تابع به نام uses_all بنویسید که یک واژه و یک رشته از حروف نیازمند را به عنوان پارامتر می‌گیرد و چنانچه اگر آن واژه همه آن حروف مورد نیاز را دست کم یکبار بکار برده باشد True برگرداند. چند واژه هستند که همه حروف صدا دارد aeiou را بکار برده اند؟ درباره aeiouy چگونه؟
تمرین ۹.۶. یک تابع به نام is_abecedarian بنویسید که چنانچه حروف در یک واژه به ترتیب الفبایی باشند (حروف دوتایی اشکالی ندارد) True برگرداند. چند واژه abecedarian وجود دارند؟
#### ۹.۳ جستجو
همه تمرین‌های در بخش پیشین یک چیز مشترک دارند؛ آنها می‌توانند با یک الگوی جستجو که در بخش ۸.۶ دیدیم حل شوند. ساده‌ترین نمونه اینگونه است:
def has_no_e(word):
for letter in word:
if letter == 'e':
return False
return True
حلقه for کاراکترهای در واژه را پیمایش می کند. اگر ما حرف “e” را پیدا کنیم، می‌توانیم بی درنگ False را برگردانیم؛ وگرنه ناگزیریم که به سراغ حرف بعدی برویم. اگر ما از حلقه به گونه‌ای نرمال بیرون رویم، به معنای آنست که ما یک “e” پیدا نکرده‌ایم، بنابراین True برمی‌گردانیم.
شما می‌توانید این تابع را با بکار بردن عملگر in کوتاهتر کنید، ولی من با این نگارش آغاز کردم چونکه این منطق الگوی جستجو را نشان می دهد.
تابع avoids نگارش عمومی‌تر has_no_e می‌باشد ولی ساختار یکسانی دارد:
def avoids(word, forbidden):
for letter in word:
if letter in forbidden:
return False
return True
ما می‌توانیم به محض اینکه یک حرف ممنوعه پیدا کنیم False برگردانیم؛ اگر به پایان حلقه برسیم True برمی‌گردانیم.
تابع uses_only نیز مشابه است بجز اینکه معنای شرط وارون است:
def uses_only(word, available):
for letter in word:
if letter not in available:
return False
return True
بجای پیمایش حروف ها در واژه، حلقه حروف مورد نیاز را پیمایش می کند. اگر هریک از حروف مورد نیاز در واژه نیامده باشد، می‌توانیم False برگردانیم.
اگر شما همانند یک دانشمند کامپیوتر بیاندیشید، شاید پی برده باشید که uses_all یک نمونه از مسأله حل شده پیشین بود، و اینگونه آنرا می نوشتید:
def uses_all(word, required):
return uses_only(required, word)
این یک مثال از برنامه‌ریزی توسعه برنامه که کاهش به مسأله حل شده پیشین نام دارد، می‌باشد که به معنای این است که مسئله‌ای را که روی آن کار می‌کنید به عنوان یک نمونه ازیک مسأله حل شده شناسایی می‌کنید و یک راه حل موجود را به آن اعمال می کنید.
#### ۹.۴ حلقه با اندیس ها
من تابع های در بخش پیشین را با حلقه های for نوشتم چونکه من تنها به کاراکترهای در رشته‌ها نیاز داشتم؛ من هیچ کاری با اندیس ها نداشتم.
برای تابع is_abecedarian ما ناگزیریم که حروف مجاور را بسنجیم و مقایسه کنیم، که کمی با حلقه for دشوار است:
def is_abecedarian(word):
previous = word[0]
for c in word:
if c < previous:
return False
previous = c
return True
یک راه دیگر این است که از روش بازگشتی بهره ببریم:
def is_abecedarian(word):
if len(word) <= 1:
return True
if word[0] > word[1]:
return False
return is_abecedarian(word[1:])
گزینه دیگر بهره گیری از حلقه while است:
def is_abecedarian(word):
i = 0
while i < len(word)-1:
if word[i+1] < word[i]:
return False
i = i+1
return True
حلقه با i=0 آغاز می‌کند و هنگامی i=len(word)-1 پایان می یابد. در هر دور، کاراکتر iام (که می‌توانید آنرا کاراکتر کنونی ببنید) را با کاراکتر i+1ام (که می‌توانید بعدی ببینید) مقایسه می کند.
اگر کاراکتر بعدی کمتر از (از دید الفبایی پیش از) از کنونی باشد، آنگاه ما یک شکست در ترند abecedarian یافته ایم، و False برمی‌گردانیم.
اگر ما به پایان حلقه بدون یافتن یک شکست برسیم، آنگاه آن واژه از آزمون گذر می کند. برای اینکه خود را متقاعد کنید که حلقه به درستی پایان می یابد، یک نمونه همانند ‘flossy’ را در لحاظ کنید. طول این واژه ۶ است، بنابراین بار پایانی که حلقه اجرا می‌شود هنگامی است که I برابر ۴ می باشد، که اندیس کاراکتر دوم از پایان می باشد. در دور پایانی، کاراکتر دوم از پایان را با کاراکتر پایانی مقایسه می کند، که همانگونه می‌شود که می خواهیم.
در اینجا نگارشی از is_palindrome (تمرین ۶.۳ را ببینید) آورده شده است که از دو اندیس بهره می گیرد؛ یکی از ابتدا آغاز می‌کند و بالاتر می رود؛ و دیگری از پایان آغاز می‌کند و پایین می آید.
def is_palindrome(word):
i = 0
j = len(word)-1
while i<j:
if word[i] != word[j]:
return False
i = i+1
j = j-1
return True
یا اینکه می‌توانیم اینرا به یک مسأله حل شده پیشین کاهش دهیم و بنویسیم:
def is_palindrome(word):
return is_reverse(word, word)
#### ۹.۵ اشکال زدایی
آزمودن برنامه‌ها دشوار است. آزمودن تابع های در این فصل نسبتاً آسان است چونکه شما می‌توانید نتایج را دستی بررسی کنید. با این حال، این جایی میان دشوار و ناممکن است که یک مجموعه از واژگان را برگزینید که برای همه خطاهای ممکن تست کنید.
با در نظر گرفتن has_no_e برای نمونه، دو مورد نمایان هستند که باید بررسی شوند: واژگانی که یک ‘e’ دارند باید False برگردانده شوند، و واژگانی که ندارند باید True برگردانند. شما نباید هیچ دردسری برای هرکدام از این‌ها داشته باشید.
درون هر مورد، زیر مورد های غیرنمایانی هستند. در میان واژگانی که یک “e” دارند، بهتر است واژگانی را با یک “e” در آغاز، در پایان، و در جایی در میانه تست کنید. بهتر است واژگان دراز، واژگان کوتاه، و واژگان خیلی کوتاه، همانند رشته خالی را تست کنید. رشته خالی یک نمونه از یک حالت خاص است، که یکی از حالت‌های غیر نمایان می‌باشد که در بیشتر موارد خطا درست می کند.
افزون بر موردهای آزمونی و تستی که خود می سازید، می‌توانید برنامه خود را با یک فهرست واژه همچون words.txt بیازمایید. با پویش خروجی، خواهید توانست که خطاها را دریابید، ولی مراقب باشید: شاید شما یک گونه از خطا را دریابید (واژگانی که نباید شامل شوند، ولی هستند) و نه دیگری (واژگانی که باید بیایند ولی نیامده اند).
به گونه کلی، آزمودن می‌تواند به شما کمک کند تا اشکالات (باگ ها) را پیدا کنید، ولی تولید کردن یک مجموعه خوب از موارد تست (test cases) آسان نیست، و هرچند اگر اینکار را انجام دهید، نمی‌توانید آسوده باشید که برنامه تان درست است. برپایه یک دانشمند کامپیوتر افسانه ای:
میتوان از تست کردن برنامه بهره جست تا بودن اشکالات را نشان داد، ولی نه هرگز برای نشان دادن نبودن آنها!
— Edsger W. Dijkstra
#### ۹.۶ واژه نامه
شیء فایل (file object): مقداری که یک فایل باز را نمایش می‌دهد.
کاهش به یک مسئله حل شده پیشین: یک راه حل کردن یک مسئله با بیان کردن آن به عنوان یک نمونه از یک مسئله حل شده پیشین.
حالت خاص: یک مورد تست که ناشناخته یا غیرنمایان باشد (و شانس کمتری برای مدیریت درست آن است).
#### تمرین‌ها ۹.۷
تمرین ۹.۷. این پرسش برپایه یک معماگو است که بر روی یک برنامه رادیویی Car Talk (http://www.cartalk.com/content/puzzler):
یک واژه با سه حرف دوتایی پشت سر هم به من دهید. من چند واژه به شما می‌دهم که تقریباً به این مسئله می خورد، ولی اینکار را نکنید. برای نمونه، واژه committee (c-o-m-m-i-t-t-e-e). این نمونه می‌توانست بسیار خوب باشد اگر که ‘i’ در میان آن سه نمی خزید. یا Mississippi: (M-i-s-s-i-s-s-i-p-p-i). اگر می توانستید آن iها را بردارید به کارمان می آمد. ولی یک واژه است که سه جفت حرف دوتایی پشت سرهم دارد و برپایه دانش من آن شاید تنها واژه‌ای با این ویژگی باشد. البته شاید بیش از ۵۰۰ واژه به اینگونه باشد ولی من تنها آنرا به یاد دارم. آن واژه چیست؟
یک برنامه بنویسید تا آنرا پیدا کند. راه حل: http://thinkpython2.com/code/cartalk1.py.
تمرین ۹.۸. در اینجا یه معمای دیگر از Car Talk آمده است که می‌توانید با یک جستجو حل کنید (http://www.cartalk.com/content/puzzlers):
“به تازگی به دیدن مادرم رفتم و ما پی بردیم که دو رقمی که سن من را می‌سازند هنگامی که وارون خوانده می‌شوند سن او را بدست می دهد. برای نمونه، اگر سن او ۷۳ است، من ۳۷ سال می شوم. ما خواستیم بدانیم که چند بار این رویداد در طی سالها رخ داده است ولی ما حواسمان با موضوع های دیگر پرت شد و به پاسخ نرسیدیم.
هنگامی که به خانه رسیدم پی بردم که رقم های سن‌مان تا کنون ۶ بار وارون پذیر بوده است. همچنین پی بردم که اگر خوش شانس باشیم به زودی بازهم در چندسال دیگر رخ می دهد، و اگر واقعاً خوش شانس باشیم یکبار دیگر هم پس از آن رخ خواهد داد. به گفته دیگر، روی هم رفته ۸ بار رخ می دهد. بنابراین پرسش این است که من چند سال دارم؟“
یک برنامه پایتون بنویسید که برای راه حل‌های این معما جستجو کند. راهنمایی: شاید متد zfill نوع رشته برای تان سودمند باشد.